package com.freedy.dataStructure.hashTable;

import java.util.ArrayList;
import java.util.StringJoiner;

/**
 * @author Freedy
 * @date 2021/3/23 16:42
 */
public class HashTable<K, T> {
    private ArrayList<LinkedList<K, T>> linkedListArr;
    private int size = 10;

    public HashTable(int size) {
        this.size = size;
        initLinkedListArr();
    }

    public HashTable() {
        initLinkedListArr();
    }

    private void initLinkedListArr() {
        linkedListArr = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            LinkedList<K, T> list = new LinkedList<>();
            linkedListArr.add(list);
        }
    }

    public void put(K key, T value) {
        LinkedList<K, T> list = linkedListArr.get(hash(key));
        Node<K, T> node = list.getNode(key);
        if (node == null) {
            list.add(key, value);
        } else {
            node.setData(value);
        }
    }

    public T get(K key) {
        LinkedList<K, T> list = linkedListArr.get(hash(key));
        return list.get(key);
    }

    public void remove(K key) {
        LinkedList<K, T> list = linkedListArr.get(hash(key));
        list.remove(key);
    }

    /**
     * 打印出hashTable的结构
     */
    public void printStructure() {
        for (int i = 0; i < size; i++) {
            LinkedList<K, T> list = linkedListArr.get(i);
            StringBuilder builder = new StringBuilder();
            builder.append("HEADER").append(i).append("-->");
            int size = list.size();
            for (int j = 0; j < size; j++) {
                builder.append(list.getNode(j).toString());
                builder.append("-->");
            }
            System.out.println(builder);
        }
    }

    /**
     * 散列函数,这里使用取模法
     */
    private int hash(K key) {
        return key.hashCode() % size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("{");
        for (int i = 0; i < size; i++) {
            LinkedList<K, T> list = linkedListArr.get(i);
            for (int j = 0; j < list.size(); j++) {
                Node<K, T> node = list.getNode(j);
                builder.append(node.getKey().toString());
                builder.append("=");
                builder.append(node.getData().toString());
                builder.append(", ");
            }
        }
        builder.delete(builder.length() - 2, builder.length());
        builder.append("}");
        return builder.toString();
    }

    /**
     * 链表类
     */
    public static class LinkedList<K, T> {
        private final Node<K, T> head;

        public LinkedList() {
            head = new Node<K, T>();
        }


        public void add(K key, T data) {
            Node<K, T> tNode = new Node<K, T>();
            tNode.setData(data);
            tNode.setKey(key);
            getNode(size() - 1).setNext(tNode);
        }


        public T get(K key) {
            for (int i = 0; i < size(); i++) {
                if (getNode(i).getKey().equals(key)) {
                    return getNode(i).getData();
                }
            }
            return null;
        }


        public T get(int index) {
            Node<K, T> node = getNode(index);
            return node.getData();
        }


        public void remove(K key) {
            //获取前置节点
            for (int i = 0; i < size(); i++) {
                if (getNode(i).getKey().equals(key)) {
                    remove(i);
                }
            }
        }

        /**
         * 删除索引
         */
        public void remove(int index) {
            //获取前置节点
            Node<K, T> pre = getNode(index - 1);
            Node<K, T> node = getNode(index);
            pre.setNext(node.getNext());
        }


        /**
         * @return 链表大小
         */
        public int size() {
            int size = 0;
            Node<K, T> temp = head.getNext();
            while (temp != null) {
                size++;
                temp = temp.getNext();
            }
            return size;
        }


        /**
         * 获取链表
         * -1 代表头节点
         */
        public Node<K, T> getNode(int index) {
            int count = -1;
            Node<K, T> temp = head;
            while (temp != null && index != count) {
                count++;
                temp = temp.getNext();
            }
            return temp;
        }


        public Node<K, T> getNode(K key) {
            for (int i = 0; i < size(); i++) {
                if (getNode(i).getKey().equals(key)) {
                    return getNode(i);
                }
            }
            return null;
        }

        @Override
        public String toString() {
            if (head.getNext() == null) {
                return "[]";
            }
            Node<K, T> temp = head.getNext();
            StringBuilder stringBuffer = new StringBuilder();
            stringBuffer.append("[");
            while (temp != null) {
                stringBuffer.append(temp.getData().toString()).append(",");
                temp = temp.getNext();  //将temp后移
            }
            stringBuffer.deleteCharAt(stringBuffer.length() - 1);
            stringBuffer.append("]");
            return stringBuffer.toString();
        }
    }

    /**
     * 节点类
     */
    public static class Node<K, T> {
        private K key;
        private T data;
        private Node<K, T> next;

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node<K, T> getNext() {
            return next;
        }

        public void setNext(Node<K, T> next) {
            this.next = next;
        }

        @Override
        public String toString() {
            return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
                    .add("key=" + key)
                    .add("data=" + data)
                    .toString();
        }
    }
}
